home *** CD-ROM | disk | FTP | other *** search
/ Complete Linux / Complete Linux.iso / docs / apps / database / ingres04.lzh / source / qrymod / trscan.c < prev    next >
Encoding:
C/C++ Source or Header  |  1985-02-08  |  7.3 KB  |  330 lines
  1. # include    <ingres.h>
  2. # include    <symbol.h>
  3. # include    <tree.h>
  4. # include    "qrymod.h"
  5. # include    <sccs.h>
  6. # include    <errors.h>
  7.  
  8. SCCSID(@(#)trscan.c    8.2    2/8/85)
  9.  
  10. /*
  11. **  AGGCHECK -- check for any aggregate in subtree.
  12. **
  13. **    This routine checks to insure that the view algorithm can
  14. **    proceed safely by checking for aggregates in the view tree.
  15. **
  16. **    Parameters:
  17. **        root -- the root of the tree to check.
  18. **
  19. **    Returns:
  20. **        TRUE -- an aggregate found.
  21. **        FALSE -- no aggregates in tree.
  22. **
  23. **    Side Effects:
  24. **        none
  25. **
  26. **    Trace Flags:
  27. **        none.
  28. */
  29.  
  30. aggcheck(root)
  31. QTREE    *root;
  32. {
  33.     register QTREE    *t;
  34.  
  35.     t = root;
  36.  
  37.     /* check for no pointer */
  38.     while (t != NULL)
  39.     {
  40.         /* check for this node an AGHEAD */
  41.         if (t->sym.type == AGHEAD)
  42.             return (TRUE);
  43.  
  44.         /* check left subtree recursively */
  45.         if (aggcheck(t->left))
  46.             return (TRUE);
  47.         
  48.         /* check right subtree iteratively */
  49.         t = t->right;
  50.     }
  51.  
  52.     return (FALSE);
  53. }
  54. /*
  55. **  VFIND -- find definition for attribute in view tree
  56. **
  57. **    The view tree is scanned for a specified RESDOM; a pointer
  58. **    to the value is returned.
  59. **
  60. **    Parameters:
  61. **        vn -- the variable number to dig out.
  62. **        vtree -- a pointer to the target list of the
  63. **            view definition tree.
  64. **
  65. **    Returns:
  66. **        a pointer to the substitution value for the specified
  67. **            'vn'.
  68. **        NULL -- if not found.
  69. **
  70. **    Side Effects:
  71. **        none
  72. **
  73. **    Trace Flags:
  74. **        none.
  75. */
  76.  
  77. QTREE *
  78. vfind(vn, vtree)
  79. int    vn;
  80. QTREE    *vtree;
  81. {
  82.     register int    n;
  83.     register QTREE    *v;
  84.  
  85.     n = vn;
  86.  
  87.     for (v = vtree; v->sym.type == RESDOM; v = v->left)
  88.     {
  89.         if (v->sym.value.sym_resdom.resno != n)
  90.             continue;
  91.  
  92.         /* found the correct replacement */
  93.         return (v->right);
  94.     }
  95.  
  96.     if (v->sym.type != TREE)
  97.         syserr("vfind: bad RESDOM node %d", v->sym.type);
  98.     return (NULL);
  99. }
  100. /*
  101. **  QSCAN -- find specified VAR node in subtree
  102. **
  103. **    Intended for finding a variable in a qualification, this
  104. **    routine just scans a tree recursively looking for a node
  105. **    with the specified VAR (varno.attno) node.
  106. **
  107. **    Parameters:
  108. **        root -- the root of the tree to scan.
  109. **        vn -- the varno to scan for.
  110. **        an -- the attno to scan for.
  111. **
  112. **    Returns:
  113. **        A pointer to the first found VAR node which matches.
  114. **            Scan is prefix.
  115. **        NULL if not found at all.
  116. **
  117. **    Side Effects:
  118. **        none
  119. **
  120. **    Trace Flags:
  121. **        none.
  122. */
  123.  
  124. QTREE *
  125. qscan(root, vn, an)
  126. QTREE    *root;
  127. int    vn;
  128. int    an;
  129. {
  130.     register QTREE    *t;
  131.     register QTREE    *u;
  132.  
  133.     t = root;
  134.  
  135.     /* check for null node */
  136.     if (t == NULL)
  137.         return (t);
  138.  
  139.     /* check to see if this node qualifies */
  140.     if (t->sym.type == VAR && t->sym.value.sym_var.varno == vn && t->sym.value.sym_var.attno == an)
  141.         return (t);
  142.  
  143.     /* check other nodes */
  144.     if ((u = qscan(t->left, vn, an)) != NULL)
  145.         return (u);
  146.     return (qscan(t->right, vn, an));
  147. }
  148. /*
  149. **  VARSET -- scan tree and set a bit vector of variables
  150. **
  151. **    The return value is a bit vector representing the set of
  152. **    variables used in that subtree.
  153. **
  154. **    Parameters:
  155. **        root -- the root of the tree to check.
  156. **
  157. **    Returns:
  158. **        A bit vector, such that bit zero (on the low order,
  159. **            right-hand end) means var zero.
  160. **
  161. **    Side Effects:
  162. **        none
  163. **
  164. **    Trace Flags:
  165. **        none
  166. */
  167.  
  168. varset(root)
  169. QTREE    *root;
  170. {
  171.     register QTREE    *t;
  172.     register int    s;
  173.  
  174.     t = root;
  175.  
  176.     if (t == NULL)
  177.         return (0);
  178.  
  179.     /* scan left and right branches */
  180.     s = varset(t->left);
  181.     s |= varset(t->right);
  182.  
  183.     /* check out this node */
  184.     if (t->sym.type == VAR)
  185.     {
  186.         /* or in bit corresponding to this varno */
  187.         s |= 1 << t->sym.value.sym_var.varno;
  188.     }
  189.  
  190.     return (s);
  191. }
  192. /*
  193. **  SUBSVARS -- scan query tree and replace VAR nodes
  194. **
  195. **    Scans a tree and finds all VAR nodes for this variable.
  196. **    These nodes are looked up in the translation tree and
  197. **    replaced by the value found there.  If this is for a
  198. **    view, the corresponding node must exist in the translation
  199. **    tree, otherwise, a 'zero' node (of a type appropriate based
  200. **    on the context) is created and inserted.
  201. **
  202. **    This routine is one half of the guts of the whole view
  203. **    algorithm.
  204. **
  205. **    VAR nodes are detached and replaced with the replacement
  206. **    as defined by the view.  Note that there can never be any
  207. **    problems here, since VAR nodes are only used in retrieve
  208. **    contexts.
  209. **
  210. **    It does some extra processing with RESDOM nodes with
  211. **    resno = 0.  These nodes specify a 'tid' domain, and are
  212. **    included by the parser on REPLACE and DELETE commands
  213. **    (for some reason decomp wants them).  Subsvars will allow
  214. **    this construct iff the right hand pointer is a VAR node
  215. **    with attno = 0.  In this case it just changes the varno
  216. **    of the VAR node to be the Qt.qt_resvar number.  This is be-
  217. **    cause the Qt.qt_resvar is the variable number of the one and
  218. **    only underlying base relation of the view on an update
  219. **    (which is presumably the only case where this can come
  220. **    up).  Vrscan has already insured that there can only be
  221. **    a single base relation in this case.
  222. **
  223. **    This whole messy thing is only done with view substitutions.
  224. **
  225. **    Parameters:
  226. **        proot -- a pointer to the pointer to the root of the
  227. **            tree to be updated.
  228. **        vn -- the varno of the view variable.  This is the
  229. **            varno which will be scanned for.
  230. **        transtree -- a pointer to the left branch (target list)
  231. **            of the translation tree.
  232. **        vmode -- mdVIEW if called from view processor, mdAPP
  233. **            if called from the integrity processor with
  234. **            an APPEND command, else something else.
  235. **            Mostly, changes the handling of TID type
  236. **            nodes, and forces an error on a view if the
  237. **            VAR node in the scanned tree does not exist
  238. **            in the vtree.
  239. **
  240. **    Returns:
  241. **        none
  242. **        (non-local on error).
  243. **
  244. **    Side Effects:
  245. **        The tree pointed to by *proot is updated in possibly
  246. **            very exciting ways.
  247. **
  248. **    Trace Flags:
  249. **        32
  250. */
  251.  
  252. subsvars(proot, vn, transtree, vmode)
  253. QTREE    **proot;
  254. int    vn;
  255. QTREE    *transtree;
  256. int    vmode;
  257. {
  258.     register QTREE    *t;
  259.     register QTREE    *v;
  260.     register int    i;
  261.     extern QTREE    *vfind();
  262.     extern QTREE    *makezero();
  263.     extern QTREE    *treedup();
  264.  
  265.     t = *proot;
  266.     v = transtree;
  267.  
  268. #    ifdef xQTR3
  269.     if (tTf(32, 0))
  270.         printf("subsvars: vn %d root %u transtree %u\n", vn, t, v);
  271. #    endif
  272.  
  273.     if (t == NULL)
  274.         return;
  275.  
  276.     /* check left branch of the tree */
  277.     subsvars(&t->left, vn, v, vmode);
  278.  
  279.     /* check for special 'tid' RESDOM (used by DEL and REPL) */
  280.     if (t->sym.type == RESDOM && t->sym.value.sym_resdom.resno == 0)
  281.     {
  282.         /* test for not Qt.qt_resvar, in which case we ignore leaf */
  283.         if (vn != Qt.qt_resvar)
  284.             return;
  285.  
  286.         /* t->right better be VAR node, attno 0 */
  287.         t = t->right;
  288.         if (t->sym.type != VAR || t->sym.value.sym_var.attno != 0 || t->sym.value.sym_var.varno != vn)
  289.             syserr("subsvars: RESDOM 0 not VAR 0 %d, %d, %d",
  290.                 vn, t->sym.value.sym_var.attno, t->sym.type);
  291.         
  292.         /* change varno to new Qm.qm_newresvar (set by vrscan) */
  293. #        ifdef xQTR3
  294.         if (tTf(32, 1))
  295.             printf("RESDOM 0: Qm.qm_newresvar %d\n", Qm.qm_newresvar);
  296. #        endif
  297.         t->sym.value.sym_var.varno = Qm.qm_newresvar;
  298.         return;
  299.     }
  300.  
  301.     /* scan right branch */
  302.     subsvars(&t->right, vn, v, vmode);
  303.  
  304.     /* check for interesting node */
  305.     if (t->sym.type != VAR || t->sym.value.sym_var.varno != vn)
  306.         return;
  307.  
  308.     /* test for special 'tid' attribute case */
  309.     if (t->sym.value.sym_var.attno == 0 && vmode == mdVIEW)
  310.     {
  311.         qmerror(VIEWTIDS, Qt.qt_qmode, vn, 0);    /* views do not have tids */
  312.     }
  313.  
  314.     /* find var in vtree */
  315.     v = vfind(t->sym.value.sym_var.attno, v);
  316.     if (v == NULL)
  317.     {
  318.         if (vmode == mdVIEW)
  319.             syserr("subsvars: attno %d", t->sym.value.sym_var.attno);
  320.         else if (vmode == mdAPP)
  321.             v = makezero();
  322.     }
  323.     else
  324.         v = treedup(v);
  325.  
  326.     /* replace VAR node */
  327.     if (v != NULL)
  328.         *proot = v;
  329. }
  330.